/*oOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoO*/
/*
Authors: Ram Ovadia 201374022 and Lior Fass 300069705
Project: HW Assignment 4 
Description: This is the module implementing Dijkstra's shprtest path algorithm used in Oiway.  
Reference: an adaptation of the algorithm published on: http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
*/
/*oOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoO*/

#include "Djikstra.h"

#define FALSE 0
#define TRUE 1

/*
 * retraces the previous array in order to transform it to an array holding the forward directed nodes indexes in the shortest path.    
 * 
 * Input:
 * -----
 * prev[] - an array holding for each node(by index), its preceding node (if exist, by index, else -1)   
 * n - number of nodes required in the graph.      
 * src/dest - index of source/destination node
 *
 * Output:
 * -----
 * 0 - succesful - prev will be rewritten to hold the indexes of the nodes in order in the shortest path. after dest prev will hold the value -1. 
 * 1 - unsuccessful 
 */ 
int retrace(int prev[], int n, int src, int dst)
{
	int *temp_route = NULL;
	int cur;
	int i = 1;
	int j = 0;

	temp_route = (int *)malloc(sizeof(int)*n);
	if (( prev == NULL ) || (temp_route == NULL ))
	{
		printf("failed to allocate mem or bad argument\r\n");
		return 1;
	}
	cur = dst;
	//reverse prev array. 
	while (cur != src)
	{
		i++;
		if (prev[cur] != -1)
		{
			temp_route[prev[cur]] = cur;
			cur = prev[cur];
		} else
		{
			printf("failed to find a path from source to dest");
			return 1;
		}
	}
	cur = src;
	//create forward going route in prev. 
	for (j=0; j<i; j++)
	{
		prev[j] = cur;
		cur = temp_route[cur];
	}
	prev[j] = -1;
	free(temp_route);
	return 0;
}


/*
 * A utility function to find the vertex with minimum distance value, from the set of vertices not yet included in shortest path tree
 * 
 * Input:
 * -----
 * dist - holds the shortest distance from src to i for each i checked. 
 * sptSet - an array holding the set of vertices in the shortest path tree.    
 * n - number of nodes required in the graph.      
 *
 * Output:
 * -----
 * index of the node with minimum distance value not included in the shortest path tree. 
 */
int minDistance(int dist[], int sptSet[], int n)
{
   // Initialize min value
   int min = INT_MAX, min_index, v;
 
   for (v = 0; v < n; v++)
     if ((sptSet[v] == FALSE) && (dist[v] <= min))
         min = dist[v], min_index = v;
 
   return min_index;
}

//int printSolution(int dist[], int prev[], int n)
//{
 //  int i;
  // printf("Vertex   Distance from Source\n");
   //for (i = 0; i < n; i++)
    //  printf("%d \t\t %d\n", i, dist[i]);
   //printf("Vertex   Previous Vertex\n");
   //for (i = 0; i < n; i++)
    //  printf("%d \t\t %d\n", i, prev[i]);
  // return 0;
//}

/*
 * Initiates a Dijkstra struct. Allocates struct and variables. tests user allocated arrays, and allocates module handled arrays. 
 * 
 * Input:
 * -----    
 * n - number of nodes required in the graph.      
 * graph - pointer to adjacency matrix represenation of the roadmap. 
 * prev - a preallocated array used in the algorithm. Will finally hold the shortest path returned to the user. 
 *
 * Output:
 * -----
 * successful - returns Dijkstra struct holding both user variables, and module allocated variables. 
 * unsuccessful - returns NULL;
 */
Djikstra *djikstra_init(int n, int *graph, int *prev)
{
	Djikstra *djikstra = NULL;
	djikstra = (Djikstra *)malloc(sizeof(Djikstra));
	if ( djikstra == NULL )
	{
		printf("Failed to allocate djikstra struct\r\n");
		return NULL;
	}
	if ( n < 1 )
	{
		printf("invalid dimension size n\r\n");
		return NULL;
	}
	djikstra->n = n;
	if ( graph == NULL )
	{
		printf("invalid graph pointer\r\n");
		return NULL;
	}
	djikstra->graph = graph;
	if ( prev == NULL )
	{
		printf("invalid prev pointer n\r\n");
		return NULL;
	}
	djikstra->prev = prev;
	djikstra->dist = (int *)malloc(sizeof(int)*n);
	djikstra->sptSet = (int *)malloc(sizeof(int)*n);
	if (( djikstra->dist == NULL ) || ( djikstra->sptSet == NULL ))
	{
		printf("failed to allocate djikstra arrays\r\n");
		return NULL;
	}
	return djikstra;
}

/*
 * Cleans a Dijkstra struct. Deallocates struct and module variables.  
 * 
 * Input:
 * -----    
 * dijkstra - Dijkstra struct used in the module. 
 *
 * Output:
 * -----
 * void. 
 */
void djikstra_clean(Djikstra *djikstra)
{
	if ( djikstra != NULL )
	{
		if (djikstra->dist != NULL)
		{
			free(djikstra->dist);
		}
		if (djikstra->sptSet != NULL)
		{
			free(djikstra->sptSet);
		}
		free(djikstra);
		djikstra = NULL;
	}
}


int djikstra(int *graph, int *prev, int n, int src, int dst)
{
	Djikstra *djikstra = NULL;
    int i, count;    
	
	djikstra = djikstra_init(n, graph, prev);
	if (djikstra == NULL)
	{
			return 1;
	}

	// dist[i] will hold the shortest
	// distance from src to i
      
	// sptSet[i] (shortest path tree) will true if vertex i is included in shortest
	// path tree or shortest distance from src to i is finalized
		
	//prev[v] will hold the index of the vertex that is previous to v in the shortest path. 

     // Initialize all distances as INFINITE and stpSet[] as false, prev[] as n/a (-1)
     for (i = 0; i < n; i++)
        djikstra->dist[i] = INT_MAX, djikstra->sptSet[i] = FALSE, prev[i] = -1;
 
     // Distance of source vertex from itself is always 0
     // makes sure first node handled is the source. 
	 djikstra->dist[src] = 0;
	 
     // Find shortest path for all vertices
     for (count = 0; count < n-1; count++)
     {
       // Pick the minimum distance vertex from the set of vertices not
       // yet processed. u is always equal to src in first iteration.
       int u = minDistance(djikstra->dist, djikstra->sptSet, n);
	   int v;
       // Mark the picked vertex as processed
       djikstra->sptSet[u] = TRUE;
 
       // Update dist value of the adjacent vertices of the picked vertex.
       for (v = 0; v < n; v++)
 
         // Update dist[v] only if is not in sptSet, there is an edge from 
         // u to v, and total weight of path from src to  v through u is 
         // smaller than current value of dist[v]
         if (!djikstra->sptSet[v] && (DGRAPH(graph, u, v, n) != -1) && djikstra->dist[u] != INT_MAX 
                                       && djikstra->dist[u]+DGRAPH(graph, u, v, n) < djikstra->dist[v])
		 {
            djikstra->dist[v] = djikstra->dist[u] + DGRAPH(graph, u, v, n);
			djikstra->prev[v] = u;
		 }
     }
 
	 djikstra_clean(djikstra);
	 return retrace(prev, n, src, dst);
}

